<?php
/*
	Solution to saving BST to a file and reading it out.
	Saving: Save the nodes in pre-order
	Asuming no negative numbers, no duplicated numbers
*/

require_once 'util.php';

importJS();

// Assume this is what we read out from a file
$input = "30 20 10 40 35 50";

echo "Input is $input<br/>";
$values = explode(' ', $input);

//$root = readBSTFromInput( $values );
$root = readBSTFromInputAwesome( $values );
bt_draw($root);

// =========================================================================
// Straight forward solution:
// Read element one by one and BST search for the position and insert.
// Since every search is O(lgn), total is O( n lg n )
function readBSTFromInput( $values ){
	$root = null;

	foreach( $values as $value ){
		$value = array_shift( $values );
		$node = new CBTNode();
		$node->value = $value;

		insertBSTRecursive( $node, $root );
	}	

	return $root;
} 

function insertBSTRecursive( $node, &$root ){
	
	if( !$root ){
		// New bst
		$root = $node;
		echo $node->value." inserted</br>";
		return;
	}

	if( $root->value > $node->value ){
		insertBSTRecursive( $node, $root->left );	
	}
	else {
		insertBSTRecursive( $node, $root->right );		
	}
}
// =========================================================================

// =========================================================================
// More efficient solution
// Keep a min and max for every recursive call.
// Important for the "recursion" mind set: the parameter to pass for every 
// recursion

function readBSTFromInputAwesome( $values ){
	$root = null;
	$value = array_shift( $values );
	$min = 0;
	$max = PHP_INT_MAX;
	insertBSTRecursiveAwesome( $min, $max, $value, $root, $values );
	return $root;
}

// Read the important note about why the $value param is a pass by reference.
function insertBSTRecursiveAwesome( $min, $max, &$value, &$node, &$values ){
	if( $value < $max && $value > $min ){
		$node = new CBTNode();
		$node->value = $value;
		echo $node->value." inserted</br>";
		$pre = $value;

		if( count($values) ){
			// Next value
			$value = array_shift( $values );
			insertBSTRecursiveAwesome( $min, $pre, $value, $node->left, $values );

			// Important:
			// If a new value in the above call of the function was not inserted,
			// The value should be set by the above call so that the new value will
			// be tried here in the right tree. 
			insertBSTRecursiveAwesome( $pre, $max, $value, $node->right, $values );
		}
	}
	else {
		// Do nothing. The upper level recursion should be handling this
		echo $value." not in range ($min, $max)</br>";
	}
}

// =========================================================================
